package test;
/*
 *ClassName:EditDistance
 *Description:编辑距离算法，返回数组的相似度
 *@author:可爱的大鸭子
 */

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class EditDistance {
    public static int minDistance(List<Integer> sourceStr, List<Integer> targetStr){
        int sourceLen = sourceStr.size();
        int targetLen = targetStr.size();

        if(sourceLen == 0){
            return targetLen;
        }
        if(targetLen == 0){
            return sourceLen;
        }

        //定义矩阵(二维数组)
        int[][]  arr = new int[sourceLen+1][targetLen+1];

        for(int i=0; i < sourceLen+1; i++){
            arr[i][0] = i;
        }
        for(int j=0; j < targetLen+1; j++){
            arr[0][j] = j;
        }

        int sourceChar ;
       int targetChar ;

        for(int i=1; i < sourceLen+1 ; i++){
            sourceChar = sourceStr.get(i-1);

            for(int j=1; j < targetLen+1 ; j++){
                targetChar = targetStr.get(j-1);

                if(sourceChar==targetChar){
                    /*
                     *  如果source[i] 等于target[j]，则：d[i, j] = d[i-1, j-1] + 0          （递推式 1）
                     */
                    arr[i][j] = arr[i-1][j-1];
                }else{
                    /*  如果source[i] 不等于target[j]，则根据插入、删除和替换三个策略，分别计算出使用三种策略得到的编辑距离，然后取最小的一个：
                        d[i, j] = min(d[i, j - 1] + 1, d[i - 1, j] + 1, d[i - 1, j - 1] + 1 )    （递推式 2）
                        >> d[i, j - 1] + 1 表示对source[i]执行插入操作后计算最小编辑距离
                        >> d[i - 1, j] + 1 表示对source[i]执行删除操作后计算最小编辑距离
                        >> d[i - 1, j - 1] + 1表示对source[i]替换成target[i]操作后计算最小编辑距离
                    */
                    arr[i][j] = (Math.min(Math.min(arr[i-1][j], arr[i][j-1]), arr[i-1][j-1])) + 1;
                }
            }
        }

        System.out.println("----------矩阵打印---------------");
        //矩阵打印
        for(int i=0;i<sourceLen+1;i++){

            for(int j=0;j<targetLen+1;j++){
                System.out.print(arr[i][j]+"\t");
            }
            System.out.println();
        }
        System.out.println("----------矩阵打印---------------");

        return arr[sourceLen][targetLen];
    }


    public static String func(List l1,List l2){
        double res;
        int count=0;
        for(int i=0;i<l1.size();i++){
            for(int j=0;j<l2.size();j++){
                if(l1.get(i)==l2.get(j)){
                    count++;
                }
            }
        }
        int num1=count;
        int num2=l1.size()+l2.size()-num1;
        res=(double)num1/num2*100.0;
        DecimalFormat df = new DecimalFormat("#.00");
        return df.format(res);
    }

    public static void main(String[] args) {
        List<Integer> l1=new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6));
        List<Integer> l2=new ArrayList<Integer>(Arrays.asList(1,2,3,4));
        int len=minDistance(l1,l2);
        String res=func(l1,l2);
        System.out.println(res);
    }
}
